package com.demo.datastructure.linkedList;

import java.util.LinkedList;

/**
 * @description: 单项链表实现回文字符串
 * 链接指针反转联系
 * @author: ljr
 * @time: 2021/4/14 17:41
 */
public class LinkedListDemo4 {

    private ListNode head;

    public static class ListNode {
        Character val;
        ListNode next;
        ListNode(Character x) { val = x; }

        public ListNode(Character val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }


    public Boolean PalindromicString(String name){
        LinkedList<Character> list = new LinkedList<>();
        for(Character character : name.toCharArray()){
            ListNode node = new ListNode(character, head);
            head = node;
        }
        return processFour();
    }

    private Boolean processOne() {
        //先找到中间节点
        ListNode next = head;
        ListNode towNext = head;
        while(towNext != null && towNext.next != null){
            next = next.next;
            towNext = towNext.next.next;
        }

        //对后段节点进行反转, 前一个节点等于后一个节点的下一个节点
        ListNode lastNext = next.next;
        ListNode prev = next;
        prev.next = null;
        while(lastNext != null){
            ListNode newNext = lastNext.next;
            lastNext.next = prev;
            prev = lastNext;
            lastNext = newNext;
        }

        //比较字符串是否一致
        ListNode one = prev;
        ListNode two = head;
        while(one != null){
            if(!one.val.equals(two.val)){
                return false;
            }
            one = one.next;
            two = two.next;
        }
        return true;
    }

    private Boolean processTwo() {
        ListNode next = head;
        ListNode towNext = head;
        ListNode prev = null;
        while(towNext != null && towNext.next != null){
            towNext = towNext.next.next;
            ListNode nextNode = next.next;
            next.next = prev;
            prev = next;
            next = nextNode;
        }

        if(towNext != null){
            next =  next.next;
        }

        ListNode one = prev;
        ListNode two = next;
        while(one != null){
            if(!one.val.equals(two.val)){
                return false;
            }
            one = one.next;
            two = two.next;
        }
        return true;
    }

    private Boolean processThree() {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }

        if(fast != null){
            slow = slow.next;
        }

        ListNode perv = null;
        while(slow != null){
            ListNode oldNode = slow.next;
            slow.next = perv;
            perv = slow;
            slow = oldNode;
        }

        while(perv != null){
            if(perv.val != head.val){
                return false;
            }
            perv = perv.next;
            head = head.next;
        }
        return true;
    }

    private Boolean processFour() {
        ListNode fast = head;
        ListNode slow = head;
        ListNode prev = null;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            ListNode nextNode = slow.next;
            slow.next = prev;
            prev = slow;
            slow = nextNode;
        }

        if(fast != null){
            slow = slow.next;
        }

        while(slow != null){
            if(slow.val != prev.val){
                return false;
            }
            slow = slow.next;
            prev = prev.next;
        }
        return true;
    }

    private Boolean processFivee() {
        ListNode fast = head;
        ListNode slow = head;
        ListNode prev = null;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            ListNode next = slow.next;
            slow.next = prev;
            prev = slow;
            slow = next;
        }

        if(fast != null){
            slow = slow.next;
        }

        while(slow != null){
            if(slow.next != prev.next){
                return false;
            }
            slow = slow.next;
            prev = prev.next;
        }
        return true;
    }

    public static void main(String[] args) {
        LinkedListDemo4 linkedListDemo4 = new LinkedListDemo4();
        //ababbaba
        System.out.println(linkedListDemo4.PalindromicString("ababaaba"));
    }


}
